package com.platform.modules.alg.alglib.poj3253;

import java.util.PriorityQueue;

public class Poj3253 {
    public String output = "";

    public String cal(String input) {
        long sum;
        int n, t, t1, t2;

        PriorityQueue<Integer> q = new PriorityQueue<>(); // 默认为小顶堆
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        for (int i = 1; i <= n; i++) {
            t = Integer.parseInt(line[i]);
            q.add(t);
        }
        sum = 0;
        if (q.size() == 1) {
            t1 = q.poll();
            sum += t1;
        }
        while (q.size() > 1) {
            t1 = q.poll();
            t2 = q.poll();
            t = t1 + t2;
            sum += t;
            q.add(t);
        }
        output=""+sum;
        return output;
    }
}
